package swordoffer.offer56_1;

public class XOR {
    /*
        nums 中一定有两个数出现了奇数次，其余数字出现了偶数次
    */
    public int[] singleNumbers(int[] nums) {
        int[] res = new int[2];
        int temp = 0;
        /*
            假设出现了奇数次的这两个数分别为 a、b
            temp 异或后的结果必然为 a ^ b，并且 a 和 b 不相等，那么 temp = a ^ b 且 != 0
            那么 temp 的二进制中必然存在一个位置上是 1（a和b不相等保证了这一点），设该位置为 x
            此时可以将数组分成两个部分：
                1. x 位置为 1 的所有整数
                2. x 位置为 0 的所有整数
            利用一个变量 onlyOne = 0，与所有 x 位置上为 1 的整数进行异或运算，可以得到 a 或 b（取决于 a、b 谁在 x 位置上为 1）
            最后 temp ^ onlyOne 即可得到另一个所求的数字
         */
        for (int i = 0; i < nums.length; i++) {
            temp = temp ^ nums[i];
        }
        // 技巧：提取最右的 1（即 x 位置）
        int rightOne = temp & (~temp + 1);
        /*
            也可以使用如下方式提取最右的 1
            int one = 1;
            while ((temp & one) == 0) {
                one <<= 1;
            }
         */
        int onlyOne = 0;
        for (int i = 0; i < nums.length; i++) {
            // 与所有 x 位置上为 1 的数字进行异或
            if ((nums[i] & rightOne) != 0) {
                onlyOne ^= nums[i];
            }
        }
        // onlyOne = a 或 b
        res[0] = onlyOne;
        // res[1] = a ^ b ^ a(b)
        res[1] = temp ^ onlyOne;
        return res;
    }
}
